![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sched_prim.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / kern|
Return to sched_prim.c CVS log | Up to [Apple Darwin 0.x] / kernel / kern |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: * Mach Operating System
27: * Copyright (c) 1993-1987 Carnegie Mellon University
28: * All Rights Reserved.
29: *
30: * Permission to use, copy, modify and distribute this software and its
31: * documentation is hereby granted, provided that both the copyright
32: * notice and this permission notice appear in all copies of the
33: * software, derivative works or modified versions, and any portions
34: * thereof, and that both notices appear in supporting documentation.
35: *
36: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
37: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
38: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
39: *
40: * Carnegie Mellon requests users of this software to return to
41: *
42: * Software Distribution Coordinator or [email protected]
43: * School of Computer Science
44: * Carnegie Mellon University
45: * Pittsburgh PA 15213-3890
46: *
47: * any improvements or extensions that they make and grant Carnegie Mellon
48: * the rights to redistribute these changes.
49: */
50: /*
51: * File: sched_prim.c
52: * Author: Avadis Tevanian, Jr.
53: * Date: 1986
54: *
55: * Scheduling primitives
56: *
57: */
58:
59: #include <cpus.h>
60: #include <simple_clock.h>
61: #include <mach_fixpri.h>
62: #include <mach_host.h>
63: #include <hw_footprint.h>
64:
65: #include <mach/machine.h>
66: #include <kern/ast.h>
67: #include <kern/counters.h>
68: #include <kern/cpu_number.h>
69: #include <kern/lock.h>
70: #include <kern/macro_help.h>
71: #include <kern/processor.h>
72: #include <kern/queue.h>
73: #include <kern/sched.h>
74: #include <kern/sched_prim.h>
75: #include <kern/syscall_subr.h>
76: #include <kern/thread.h>
77: #include <kern/thread_swap.h>
78: #include <kern/time_out.h>
79: #include <vm/pmap.h>
80: #include <vm/vm_kern.h>
81: #include <vm/vm_map.h>
82: #include <machine/machspl.h> /* For def'n of splsched() */
83:
84: #if MACH_FIXPRI
85: #include <mach/policy.h>
86: #endif /* MACH_FIXPRI */
87:
88: #import <kern/assert.h>
89: #import <kern/power.h>
90:
91: extern int hz;
92:
93: #define DEFAULT_PREEMPTION_RATE 100 /* (1/s) */
94: int default_preemption_rate = DEFAULT_PREEMPTION_RATE;
95: int min_quantum;
96:
97: unsigned sched_tick;
98:
99: #if SIMPLE_CLOCK
100: int sched_usec;
101: #endif /* SIMPLE_CLOCK */
102:
103: thread_t sched_thread_id;
104:
105: void recompute_priorities(void); /* forward */
106: void update_priority(thread_t);
107: void set_pri(thread_t, int, boolean_t);
108: void do_thread_scan(void);
109:
110: thread_t choose_pset_thread();
111:
112: #define RUNQ_DEBUG 0
113:
114: #if RUNQ_DEBUG
115: int runq_debug = 0;
116:
117: #define CHECKRQ(rq, s) \
118: if (runq_debug) checkrq((rq), (s))
119:
120: #define THREAD_CHECK(th, rq) \
121: if (runq_debug) thread_check((th), (rq))
122:
123: void checkrq(run_queue_t, char *);
124: void thread_check(thread_t, run_queue_t);
125: #endif
126:
127: /*
128: * State machine
129: *
130: * states are combinations of:
131: * R running
132: * W waiting (or on wait queue)
133: * S suspended (or will suspend)
134: * N non-interruptible
135: *
136: * init action
137: * assert_wait thread_block clear_wait suspend resume
138: *
139: * R RW, RWN R; setrun - RS -
140: * RS RWS, RWNS S; wake_active - - R
141: * RN RWN RN; setrun - RNS -
142: * RNS RWNS RNS; setrun - - RN
143: *
144: * RW W R RWS -
145: * RWN WN RN RWNS -
146: * RWS WS; wake_active RS - RW
147: * RWNS WNS RNS - RWN
148: *
149: * W R; setrun WS -
150: * WN RN; setrun WNS -
151: * WNS RNS; setrun - WN
152: *
153: * S - - R
154: * WS S - W
155: *
156: */
157:
158: /*
159: * Waiting protocols and implementation:
160: *
161: * Each thread may be waiting for exactly one event; this event
162: * is set using assert_wait(). That thread may be awakened either
163: * by performing a thread_wakeup_prim() on its event,
164: * or by directly waking that thread up with clear_wait().
165: *
166: * The implementation of wait events uses a hash table. Each
167: * bucket is queue of threads having the same hash function
168: * value; the chain for the queue (linked list) is the run queue
169: * field. [It is not possible to be waiting and runnable at the
170: * same time.]
171: *
172: * Locks on both the thread and on the hash buckets govern the
173: * wait event field and the queue chain field. Because wakeup
174: * operations only have the event as an argument, the event hash
175: * bucket must be locked before any thread.
176: *
177: * Scheduling operations may also occur at interrupt level; therefore,
178: * interrupts below splsched() must be prevented when holding
179: * thread or hash bucket locks.
180: *
181: * The wait event hash table declarations are as follows:
182: */
183:
184: #define NUMQUEUES 59
185:
186: queue_head_t wait_queue[NUMQUEUES];
187: decl_simple_lock_data(, wait_lock[NUMQUEUES])
188:
189: /* NOTE: we want a small positive integer out of this */
190: #define wait_hash(event) \
191: ((((int)(event) < 0) ? ~(int)(event) : (int)(event)) % NUMQUEUES)
192:
193: void wait_queue_init(void)
194: {
195: register int i;
196:
197: for (i = 0; i < NUMQUEUES; i++) {
198: queue_init(&wait_queue[i]);
199: simple_lock_init(&wait_lock[i]);
200: }
201: }
202:
203: void sched_init(void)
204: {
205: /*
206: * Calculate the minimum quantum
207: * in ticks.
208: */
209: if (default_preemption_rate < 1)
210: default_preemption_rate = DEFAULT_PREEMPTION_RATE;
211: min_quantum = hz / default_preemption_rate;
212: /*
213: * Round up result (4/5) to an
214: * integral number of ticks.
215: */
216: if (((hz * 10) / default_preemption_rate) - (min_quantum * 10) >= 5)
217: min_quantum++;
218: if (min_quantum < 1)
219: min_quantum = 1;
220:
221: wait_queue_init();
222: pset_sys_bootstrap(); /* initialize processer mgmt. */
223: queue_init(&action_queue);
224: simple_lock_init(&action_lock);
225: sched_tick = 0;
226: #if SIMPLE_CLOCK
227: sched_usec = 0;
228: #endif /* SIMPLE_CLOCK */
229: ast_init();
230: }
231:
232: /*
233: * Thread timeout routine, called when timer expires.
234: * Called at splsoftclock.
235: */
236: void thread_timeout(
237: thread_t thread)
238: {
239: assert(thread->timer.set == TELT_UNSET);
240:
241: clear_wait(thread, THREAD_TIMED_OUT, FALSE);
242: }
243:
244: /*
245: * thread_set_timeout:
246: *
247: * Set a timer for the current thread, if the thread
248: * is ready to wait. Must be called between assert_wait()
249: * and thread_block().
250: */
251:
252: void thread_set_timeout(
253: int t) /* timeout interval in ticks */
254: {
255: register thread_t thread = current_thread();
256: register spl_t s;
257:
258: s = splsched();
259: thread_lock(thread);
260: if ((thread->state & TH_WAIT) != 0) {
261: set_timeout(&thread->timer, t);
262: }
263: thread_unlock(thread);
264: splx(s);
265: }
266:
267: /*
268: * Set up thread timeout element when thread is created.
269: */
270: void thread_timeout_setup(
271: register thread_t thread)
272: {
273: thread->timer.fcn = (int (*)())thread_timeout;
274: thread->timer.param = (char *)thread;
275: thread->depress_timer.fcn = (int (*)())thread_depress_timeout;
276: thread->depress_timer.param = (char *)thread;
277: }
278:
279: /*
280: * assert_wait:
281: *
282: * Assert that the current thread is about to go to
283: * sleep until the specified event occurs.
284: */
285: void assert_wait(
286: event_t event,
287: boolean_t interruptible)
288: {
289: register queue_t q;
290: register int index;
291: register thread_t thread;
292: #if MACH_SLOCKS
293: register simple_lock_t lock;
294: #endif /* MACH_SLOCKS */
295: spl_t s;
296:
297: thread = current_thread();
298: if (thread->wait_event != 0) {
299: printf("assert_wait: already asserted event 0x%x\n",
300: thread->wait_event);
301: panic("assert_wait");
302: }
303: s = splsched();
304: if (event != 0) {
305: index = wait_hash(event);
306: q = &wait_queue[index];
307: #if MACH_SLOCKS
308: lock = &wait_lock[index];
309: #endif /* MACH_SLOCKS */
310: simple_lock(lock);
311: thread_lock(thread);
312: enqueue_tail(q, (queue_entry_t) thread);
313: thread->wait_event = event;
314: if (interruptible)
315: thread->state |= TH_WAIT;
316: else
317: thread->state |= TH_WAIT | TH_UNINT;
318: thread_unlock(thread);
319: simple_unlock(lock);
320: }
321: else {
322: thread_lock(thread);
323: if (interruptible)
324: thread->state |= TH_WAIT;
325: else
326: thread->state |= TH_WAIT | TH_UNINT;
327: thread_unlock(thread);
328: }
329: splx(s);
330: }
331:
332: /*
333: * clear_wait:
334: *
335: * Clear the wait condition for the specified thread. Start the thread
336: * executing if that is appropriate.
337: *
338: * parameters:
339: * thread thread to awaken
340: * result Wakeup result the thread should see
341: * interrupt_only Don't wake up the thread if it isn't
342: * interruptible.
343: */
344: void clear_wait(
345: register thread_t thread,
346: int result,
347: boolean_t interrupt_only)
348: {
349: register int index;
350: register queue_t q;
351: #if MACH_SLOCKS
352: register simple_lock_t lock;
353: #endif /* MACH_SLOCKS */
354: register event_t event;
355: spl_t s;
356:
357: s = splsched();
358: thread_lock(thread);
359: if (interrupt_only && (thread->state & TH_UNINT)) {
360: /*
361: * can`t interrupt thread
362: */
363: thread_unlock(thread);
364: splx(s);
365: return;
366: }
367:
368: event = thread->wait_event;
369: if (event != 0) {
370: thread_unlock(thread);
371: index = wait_hash(event);
372: q = &wait_queue[index];
373: #if MACH_SLOCKS
374: lock = &wait_lock[index];
375: #endif /* MACH_SLOCKS */
376: simple_lock(lock);
377: /*
378: * If the thread is still waiting on that event,
379: * then remove it from the list. If it is waiting
380: * on a different event, or no event at all, then
381: * someone else did our job for us.
382: */
383: thread_lock(thread);
384: if (thread->wait_event == event) {
385: remqueue(q, (queue_entry_t)thread);
386: thread->wait_event = 0;
387: event = 0; /* cause to run below */
388: }
389: simple_unlock(lock);
390: }
391: if (event == 0) {
392: register int state = thread->state;
393:
394: reset_timeout_check(&thread->timer);
395:
396: switch (state & TH_SCHED_STATE) {
397: case TH_WAIT | TH_SUSP | TH_UNINT:
398: case TH_WAIT | TH_UNINT:
399: case TH_WAIT:
400: /*
401: * Sleeping and not suspendable - put
402: * on run queue.
403: */
404: thread->state = (state &~ TH_WAIT) | TH_RUN;
405: thread->wait_result = result;
406: thread_setrun(thread, TRUE);
407: break;
408:
409: case TH_WAIT | TH_SUSP:
410: case TH_RUN | TH_WAIT:
411: case TH_RUN | TH_WAIT | TH_SUSP:
412: case TH_RUN | TH_WAIT | TH_UNINT:
413: case TH_RUN | TH_WAIT | TH_SUSP | TH_UNINT:
414: /*
415: * Either already running, or suspended.
416: */
417: thread->state = state &~ TH_WAIT;
418: thread->wait_result = result;
419: break;
420:
421: default:
422: /*
423: * Not waiting.
424: */
425: break;
426: }
427: }
428: thread_unlock(thread);
429: splx(s);
430: }
431:
432: /*
433: * thread_wakeup_prim:
434: *
435: * Common routine for thread_wakeup, thread_wakeup_with_result,
436: * and thread_wakeup_one.
437: *
438: */
439: void thread_wakeup_prim(
440: event_t event,
441: boolean_t one_thread,
442: int result)
443: {
444: register queue_t q;
445: register int index;
446: register thread_t thread, next_th;
447: #if MACH_SLOCKS
448: register simple_lock_t lock;
449: #endif /* MACH_SLOCKS */
450: spl_t s;
451: register int state;
452:
453: index = wait_hash(event);
454: q = &wait_queue[index];
455: s = splsched();
456: #if MACH_SLOCKS
457: lock = &wait_lock[index];
458: #endif /* MACH_SLOCKS */
459: simple_lock(lock);
460: thread = (thread_t) queue_first(q);
461: while (!queue_end(q, (queue_entry_t)thread)) {
462: next_th = (thread_t) queue_next((queue_t) thread);
463:
464: if (thread->wait_event == event) {
465: thread_lock(thread);
466: remqueue(q, (queue_entry_t) thread);
467: thread->wait_event = 0;
468: reset_timeout_check(&thread->timer);
469:
470: state = thread->state;
471: switch (state & TH_SCHED_STATE) {
472:
473: case TH_WAIT | TH_SUSP | TH_UNINT:
474: case TH_WAIT | TH_UNINT:
475: case TH_WAIT:
476: /*
477: * Sleeping and not suspendable - put
478: * on run queue.
479: */
480: thread->state = (state &~ TH_WAIT) | TH_RUN;
481: thread->wait_result = result;
482: thread_setrun(thread, TRUE);
483: break;
484:
485: case TH_WAIT | TH_SUSP:
486: case TH_RUN | TH_WAIT:
487: case TH_RUN | TH_WAIT | TH_SUSP:
488: case TH_RUN | TH_WAIT | TH_UNINT:
489: case TH_RUN | TH_WAIT | TH_SUSP | TH_UNINT:
490: /*
491: * Either already running, or suspended.
492: */
493: thread->state = state &~ TH_WAIT;
494: thread->wait_result = result;
495: break;
496:
497: default:
498: panic("thread_wakeup");
499: break;
500: }
501: thread_unlock(thread);
502: if (one_thread)
503: break;
504: }
505: thread = next_th;
506: }
507: simple_unlock(lock);
508: splx(s);
509: }
510:
511: /*
512: * thread_sleep:
513: *
514: * Cause the current thread to wait until the specified event
515: * occurs. The specified lock is unlocked before releasing
516: * the cpu. (This is a convenient way to sleep without manually
517: * calling assert_wait).
518: */
519: void thread_sleep(
520: event_t event,
521: simple_lock_t lock,
522: boolean_t interruptible)
523: {
524: assert_wait(event, interruptible); /* assert event */
525: simple_unlock(lock); /* release the lock */
526: thread_block_with_continuation((void (*)()) 0); /* block ourselves */
527: }
528:
529: /*
530: * thread_bind:
531: *
532: * Force a thread to execute on the specified processor.
533: * If the thread is currently executing, it may wait until its
534: * time slice is up before switching onto the specified processor.
535: *
536: * A processor of PROCESSOR_NULL causes the thread to be unbound.
537: * xxx - DO NOT export this to users.
538: */
539: void thread_bind(
540: register thread_t thread,
541: processor_t processor)
542: {
543: spl_t s;
544:
545: s = splsched();
546: thread_lock(thread);
547: thread->bound_processor = processor;
548: thread_unlock(thread);
549: (void) splx(s);
550: }
551:
552: /*
553: * Select a thread for this processor (the current processor) to run.
554: * May select the current thread.
555: * Assumes splsched.
556: */
557:
558: thread_t thread_select(
559: register processor_t myprocessor)
560: {
561: register thread_t thread = current_thread();
562:
563: myprocessor->first_quantum = TRUE;
564: /*
565: * Check for obvious simple case; local runq is
566: * empty and global runq has entry at hint.
567: */
568: if (myprocessor->runq.count > 0) {
569: thread = choose_thread(myprocessor);
570: myprocessor->quantum = min_quantum;
571: }
572: else {
573: register processor_set_t pset;
574:
575: #if MACH_HOST
576: pset = myprocessor->processor_set;
577: #else /* MACH_HOST */
578: pset = &default_pset;
579: #endif /* MACH_HOST */
580: simple_lock(&pset->runq.lock);
581: #if RUNQ_DEBUG
582: CHECKRQ(&pset->runq, "thread_select");
583: #endif /* DEBUG */
584: if (pset->runq.count == 0 ||
585: pset->runq.high < thread->sched_pri) {
586: /*
587: * Nothing else runnable. Return if this
588: * thread is still runnable on this processor.
589: * Check for priority update if required.
590: */
591: if ((thread->state == TH_RUN) &&
592: #if MACH_HOST
593: (thread->processor_set == pset) &&
594: #endif /* MACH_HOST */
595: ((thread->bound_processor == PROCESSOR_NULL) ||
596: (thread->bound_processor == myprocessor))) {
597:
598: simple_unlock(&pset->runq.lock);
599: thread_lock(thread);
600: if (thread->sched_stamp != sched_tick)
601: update_priority(thread);
602: thread_unlock(thread);
603: }
604: else {
605: thread = choose_pset_thread(myprocessor, pset);
606: }
607: }
608: else {
609: register queue_t q;
610:
611: /*
612: * If there is a thread at hint, grab it,
613: * else call choose_pset_thread.
614: */
615: q = pset->runq.runq + pset->runq.high;
616:
617: if (queue_empty(q)) {
618: pset->runq.high--;
619: thread = choose_pset_thread(myprocessor, pset);
620: }
621: else {
622: thread = (thread_t) dequeue_head(q);
623: thread->runq = RUN_QUEUE_NULL;
624: pset->runq.count--;
625: #if MACH_FIXPRI
626: /*
627: * Cannot lazy evaluate pset->runq.low for
628: * fixed priority policy
629: */
630: if ((pset->runq.count > 0) &&
631: (pset->policies & POLICY_FIXEDPRI)) {
632: while (queue_empty(q)) {
633: pset->runq.high--;
634: q--;
635: }
636: }
637: #endif /* MACH_FIXPRI */
638: #if RUNQ_DEBUG
639: CHECKRQ(&pset->runq, "thread_select: after");
640: #endif /* DEBUG */
641: simple_unlock(&pset->runq.lock);
642: }
643: }
644:
645: #if MACH_FIXPRI
646: if (thread->policy != POLICY_FIXEDPRI) {
647: #endif /* MACH_FIXPRI */
648: myprocessor->quantum = pset->set_quantum;
649: #if MACH_FIXPRI
650: }
651: else {
652: /*
653: * POLICY_FIXEDPRI
654: */
655: myprocessor->quantum = thread->sched_data;
656: }
657: #endif /* MACH_FIXPRI */
658: }
659:
660: return thread;
661: }
662:
663: /*
664: * Stop running the current thread and start running the new thread.
665: * If continuation is non-zero, and the current thread is blocked,
666: * then it will resume by executing continuation on a new stack.
667: * Returns TRUE if the hand-off succeeds.
668: * Assumes splsched.
669: */
670:
671: boolean_t thread_invoke(
672: register thread_t old_thread,
673: continuation_t continuation,
674: register thread_t new_thread)
675: {
676: /*
677: * Check for invoking the same thread.
678: */
679: if (old_thread == new_thread) {
680: /*
681: * Mark thread interruptible.
682: * Run continuation if there is one.
683: */
684: thread_lock(new_thread);
685: new_thread->state &= ~TH_UNINT;
686: thread_unlock(new_thread);
687:
688: if (continuation != (void (*)()) 0) {
689: (void) spl0();
690: call_continuation(continuation);
691: /*NOTREACHED*/
692: }
693: return TRUE;
694: }
695:
696: /*
697: * Check for stack-handoff.
698: */
699: thread_lock(new_thread);
700: if ((old_thread->stack_privilege != current_stack()) &&
701: (continuation != (void (*)()) 0))
702: {
703: switch (new_thread->state & TH_SWAP_STATE) {
704: case TH_SWAPPED:
705:
706: new_thread->state &= ~(TH_SWAPPED | TH_UNINT);
707: thread_unlock(new_thread);
708:
709: #if NCPUS > 1
710: new_thread->last_processor = current_processor();
711: #endif /* NCPUS > 1 */
712:
713: /*
714: * Set up ast context of new thread and
715: * switch to its timer.
716: */
717: ast_context(new_thread, cpu_number());
718: timer_switch(&new_thread->system_timer);
719:
720: old_thread->swap_func = continuation;
721: stack_handoff(old_thread, new_thread);
722:
723: /*
724: * We can dispatch the old thread now.
725: * This is like thread_dispatch, except
726: * that the old thread is left swapped
727: * *without* freeing its stack.
728: * This path is also much more frequent
729: * than actual calls to thread_dispatch.
730: */
731:
732: thread_lock(old_thread);
733:
734: switch (old_thread->state) {
735: case TH_RUN | TH_SUSP:
736: case TH_RUN | TH_SUSP | TH_HALTED:
737: case TH_RUN | TH_WAIT | TH_SUSP:
738: /*
739: * Suspend the thread
740: */
741: old_thread->state = (old_thread->state & ~TH_RUN)
742: | TH_SWAPPED;
743: if (old_thread->wake_active) {
744: old_thread->wake_active = FALSE;
745: thread_unlock(old_thread);
746: thread_wakeup((event_t)&old_thread->wake_active);
747:
748: goto after_old_thread;
749: }
750: break;
751:
752: case TH_RUN | TH_SUSP | TH_UNINT:
753: case TH_RUN | TH_UNINT:
754: case TH_RUN:
755: /*
756: * We can`t suspend the thread yet,
757: * or it`s still running.
758: * Put back on a run queue.
759: */
760: old_thread->state |= TH_SWAPPED;
761: thread_setrun(old_thread, FALSE);
762: break;
763:
764: case TH_RUN | TH_WAIT | TH_SUSP | TH_UNINT:
765: case TH_RUN | TH_WAIT | TH_UNINT:
766: case TH_RUN | TH_WAIT:
767: /*
768: * Waiting, and not suspendable.
769: */
770: old_thread->state = (old_thread->state & ~TH_RUN)
771: | TH_SWAPPED;
772: break;
773:
774: case TH_RUN | TH_IDLE:
775: /*
776: * Drop idle thread -- it is already in
777: * idle_thread_array.
778: */
779: old_thread->state = TH_RUN | TH_IDLE | TH_SWAPPED;
780: break;
781:
782: default:
783: printf("illegal handoff thread state 0x%x\n",
784: old_thread->state);
785: panic("thread_invoke");
786: }
787: thread_unlock(old_thread);
788: after_old_thread:
789:
790: /*
791: * call_continuation calls the continuation
792: * after resetting the current stack pointer
793: * to recover stack space. If we called
794: * the continuation directly, we would risk
795: * running out of stack.
796: */
797:
798: counter_always(c_thread_invoke_hits++);
799: (void) spl0();
800: call_continuation(new_thread->swap_func);
801: /*NOTREACHED*/
802: return TRUE; /* help for the compiler */
803:
804: case TH_SW_COMING_IN:
805: /*
806: * Waiting for a stack
807: */
808: thread_swapin(new_thread);
809: thread_unlock(new_thread);
810: counter_always(c_thread_invoke_misses++);
811: return FALSE;
812:
813: case 0:
814: /*
815: * Already has a stack - can`t handoff.
816: */
817: break;
818: }
819: }
820:
821: else {
822: /*
823: * Check that the thread is swapped-in.
824: */
825: if (new_thread->state & TH_SWAPPED) {
826: if ((new_thread->state & TH_SW_COMING_IN) ||
827: !stack_alloc_try(new_thread, thread_continue))
828: {
829: thread_swapin(new_thread);
830: thread_unlock(new_thread);
831: counter_always(c_thread_invoke_misses++);
832: return FALSE;
833: }
834: }
835: }
836:
837: new_thread->state &= ~(TH_SWAPPED | TH_UNINT);
838: thread_unlock(new_thread);
839:
840: /*
841: * Thread is now interruptible.
842: */
843: #if NCPUS > 1
844: new_thread->last_processor = current_processor();
845: #endif /* NCPUS > 1 */
846:
847: /*
848: * Set up ast context of new thread and switch to its timer.
849: */
850: ast_context(new_thread, cpu_number());
851: timer_switch(&new_thread->system_timer);
852:
853: /*
854: * switch_context is machine-dependent. It does the
855: * machine-dependent components of a context-switch, like
856: * changing address spaces. It updates active_threads.
857: * It returns only if a continuation is not supplied.
858: */
859: counter_always(c_thread_invoke_csw++);
860: old_thread = switch_context(old_thread, continuation, new_thread);
861:
862: /*
863: * We're back. Now old_thread is the thread that resumed
864: * us, and we have to dispatch it.
865: */
866: thread_dispatch(old_thread);
867:
868: return TRUE;
869: }
870:
871: /*
872: * thread_continue:
873: *
874: * Called when the current thread is given a new stack.
875: * Called at splsched.
876: */
877: void thread_continue(
878: register thread_t old_thread)
879: {
880: register continuation_t continuation = current_thread()->swap_func;
881:
882: /*
883: * We must dispatch the old thread and then
884: * call the current thread's continuation.
885: * There might not be an old thread, if we are
886: * the first thread to run on this processor.
887: */
888:
889: if (old_thread != THREAD_NULL)
890: thread_dispatch(old_thread);
891: (void) spl0();
892: (*continuation)();
893: /*NOTREACHED*/
894: }
895:
896:
897: /*
898: * thread_block:
899: *
900: * Block the current thread. If the thread is runnable
901: * then someone must have woken it up between its request
902: * to sleep and now. In this case, it goes back on a
903: * run queue.
904: *
905: * If a continuation is specified, then thread_block will
906: * attempt to discard the thread's kernel stack. When the
907: * thread resumes, it will execute the continuation function
908: * on a new kernel stack.
909: */
910:
911: void thread_block_with_continuation(
912: continuation_t continuation)
913: {
914: register thread_t thread = current_thread();
915: register processor_t myprocessor = cpu_to_processor(cpu_number());
916: register thread_t new_thread;
917: spl_t s;
918:
919: s = splsched();
920:
921: #if FAST_TAS
922: {
923: extern void recover_ras();
924:
925: if (csw_needed(thread, myprocessor))
926: recover_ras(thread);
927: }
928: #endif /* FAST_TAS */
929:
930: ast_off(cpu_number(), AST_BLOCK);
931:
932: do
933: new_thread = thread_select(myprocessor);
934: while (!thread_invoke(thread, continuation, new_thread));
935:
936: splx(s);
937: }
938:
939: /*
940: * thread_run:
941: *
942: * Switch directly from the current thread to a specified
943: * thread. Both the current and new threads must be
944: * runnable.
945: *
946: * If a continuation is specified, then thread_block will
947: * attempt to discard the current thread's kernel stack. When the
948: * thread resumes, it will execute the continuation function
949: * on a new kernel stack.
950: */
951: void thread_run(
952: continuation_t continuation,
953: register thread_t new_thread)
954: {
955: register thread_t thread = current_thread();
956: register processor_t myprocessor = cpu_to_processor(cpu_number());
957: spl_t s;
958:
959: s = splsched();
960:
961: while (!thread_invoke(thread, continuation, new_thread))
962: new_thread = thread_select(myprocessor);
963:
964: splx(s);
965: }
966:
967: /*
968: * Dispatches a running thread that is not on a runq.
969: * Called at splsched.
970: */
971:
972: void thread_dispatch(
973: register thread_t thread)
974: {
975: /*
976: * If we are discarding the thread's stack, we must do it
977: * before the thread has a chance to run.
978: */
979:
980: thread_lock(thread);
981:
982: if (thread->swap_func != (void (*)()) 0) {
983: assert((thread->state & TH_SWAP_STATE) == 0);
984: thread->state |= TH_SWAPPED;
985: stack_free(thread);
986: }
987:
988: switch (thread->state &~ TH_SWAP_STATE) {
989: case TH_RUN | TH_SUSP:
990: case TH_RUN | TH_SUSP | TH_HALTED:
991: case TH_RUN | TH_WAIT | TH_SUSP:
992: /*
993: * Suspend the thread
994: */
995: thread->state &= ~TH_RUN;
996: if (thread->wake_active) {
997: thread->wake_active = FALSE;
998: thread_unlock(thread);
999: thread_wakeup((event_t)&thread->wake_active);
1000: return;
1001: }
1002: break;
1003:
1004: case TH_RUN | TH_SUSP | TH_UNINT:
1005: case TH_RUN | TH_UNINT:
1006: case TH_RUN:
1007: /*
1008: * No reason to stop. Put back on a run queue.
1009: */
1010: thread_setrun(thread, FALSE);
1011: break;
1012:
1013: case TH_RUN | TH_WAIT | TH_SUSP | TH_UNINT:
1014: case TH_RUN | TH_WAIT | TH_UNINT:
1015: case TH_RUN | TH_WAIT:
1016: /*
1017: * Waiting, and not suspended.
1018: */
1019: thread->state &= ~TH_RUN;
1020: break;
1021:
1022: case TH_RUN | TH_IDLE:
1023: /*
1024: * Drop idle thread -- it is already in
1025: * idle_thread_array.
1026: */
1027: break;
1028:
1029: default:
1030: panic("thread_dispatch");
1031: }
1032: thread_unlock(thread);
1033: }
1034:
1035:
1036: /*
1037: * Define shifts for simulating (5/8)**n
1038: */
1039:
1040: shift_data_t wait_shift[32] = {
1041: {1,1},{1,3},{1,-3},{2,-7},{3,5},{3,-5},{4,-8},{5,7},
1042: {5,-7},{6,-10},{7,10},{7,-9},{8,-11},{9,12},{9,-11},{10,-13},
1043: {11,14},{11,-13},{12,-15},{13,17},{13,-15},{14,-17},{15,19},{16,18},
1044: {16,-19},{17,22},{18,20},{18,-20},{19,26},{20,22},{20,-22},{21,-27}};
1045:
1046: /*
1047: * do_priority_computation:
1048: *
1049: * Calculate new priority for thread based on its base priority plus
1050: * accumulated usage. PRI_SHIFT and PRI_SHIFT_2 convert from
1051: * usage to priorities. SCHED_SHIFT converts for the scaling
1052: * of the sched_usage field by SCHED_SCALE. This scaling comes
1053: * from the multiplication by sched_load (thread_timer_delta)
1054: * in sched.h. sched_load is calculated as a scaled overload
1055: * factor in compute_mach_factor (mach_factor.c).
1056: */
1057:
1058: #ifdef PRI_SHIFT_2
1059: #if PRI_SHIFT_2 > 0
1060: #define do_priority_computation(th, pri) \
1061: MACRO_BEGIN \
1062: (pri) = (th)->priority /* start with base priority */ \
1063: - ((th)->sched_usage >> (PRI_SHIFT + SCHED_SHIFT)) \
1064: - ((th)->sched_usage >> (PRI_SHIFT_2 + SCHED_SHIFT)); \
1065: if ((pri) < 0) (pri) = 0; \
1066: MACRO_END
1067: #else PRI_SHIFT_2
1068: #define do_priority_computation(th, pri) \
1069: MACRO_BEGIN \
1070: (pri) = (th)->priority /* start with base priority */ \
1071: - ((th)->sched_usage >> (PRI_SHIFT + SCHED_SHIFT)) \
1072: + ((th)->sched_usage >> (SCHED_SHIFT - PRI_SHIFT_2)); \
1073: if ((pri) < 0) (pri) = 0; \
1074: MACRO_END
1075: #endif PRI_SHIFT_2
1076: #else defined(PRI_SHIFT_2)
1077: #define do_priority_computation(th, pri) \
1078: MACRO_BEGIN \
1079: (pri) = (th)->priority /* start with base priority */ \
1080: - ((th)->sched_usage >> (PRI_SHIFT + SCHED_SHIFT)); \
1081: if ((pri) < 0) (pri) = 0; \
1082: MACRO_END
1083: #endif defined(PRI_SHIFT_2)
1084:
1085: /*
1086: * compute_priority:
1087: *
1088: * Compute the effective priority of the specified thread.
1089: * The effective priority computation is as follows:
1090: *
1091: * Take the base priority for this thread and add
1092: * to it an increment derived from its cpu_usage.
1093: *
1094: * The thread *must* be locked by the caller.
1095: */
1096:
1097: void compute_priority(
1098: register thread_t thread,
1099: boolean_t resched)
1100: {
1101: register int pri;
1102:
1103: #if MACH_FIXPRI
1104: if (thread->policy != POLICY_FIXEDPRI) {
1105: #endif /* MACH_FIXPRI */
1106: do_priority_computation(thread, pri);
1107: if (thread->depress_priority < 0)
1108: set_pri(thread, pri, resched);
1109: else
1110: thread->depress_priority = pri;
1111: #if MACH_FIXPRI
1112: }
1113: else {
1114: set_pri(thread, thread->priority, resched);
1115: }
1116: #endif /* MACH_FIXPRI */
1117: }
1118:
1119: /*
1120: * compute_my_priority:
1121: *
1122: * Version of compute priority for current thread or thread
1123: * being manipulated by scheduler (going on or off a runq).
1124: * Only used for priority updates. Policy or priority changes
1125: * must call compute_priority above. Caller must have thread
1126: * locked and know it is timesharing and not depressed.
1127: */
1128:
1129: void compute_my_priority(
1130: register thread_t thread)
1131: {
1132: register int temp_pri;
1133:
1134: do_priority_computation(thread,temp_pri);
1135: thread->sched_pri = temp_pri;
1136: }
1137:
1138: /*
1139: * recompute_priorities:
1140: *
1141: * Update the priorities of all threads periodically.
1142: */
1143: void recompute_priorities(void)
1144: {
1145: static int recompute_priority_ticks;
1146: #if SIMPLE_CLOCK
1147: int new_usec;
1148: #endif /* SIMPLE_CLOCK */
1149:
1150: if (recompute_priority_ticks-- > 0)
1151: return;
1152:
1153: sched_tick++; /* age usage one more time */
1154: #if SIMPLE_CLOCK
1155: /*
1156: * Compensate for clock drift. sched_usec is an
1157: * exponential average of the number of microseconds in
1158: * a second. It decays in the same fashion as cpu_usage.
1159: */
1160: new_usec = sched_usec_elapsed();
1161: sched_usec = (5*sched_usec + 3*new_usec)/8;
1162: #endif /* SIMPLE_CLOCK */
1163: /*
1164: * Wakeup scheduler thread.
1165: */
1166: if (sched_thread_id != THREAD_NULL) {
1167: clear_wait(sched_thread_id, THREAD_AWAKENED, FALSE);
1168: }
1169:
1170: recompute_priority_ticks = hz;
1171: }
1172:
1173: /*
1174: * update_priority
1175: *
1176: * Cause the priority computation of a thread that has been
1177: * sleeping or suspended to "catch up" with the system. Thread
1178: * *MUST* be locked by caller. If thread is running, then this
1179: * can only be called by the thread on itself.
1180: */
1181: void update_priority(
1182: register thread_t thread)
1183: {
1184: register unsigned int ticks;
1185: register shift_t shiftp;
1186: register int temp_pri;
1187:
1188: ticks = sched_tick - thread->sched_stamp;
1189:
1190: assert(ticks != 0);
1191:
1192: if ((thread->state & TH_RUN) == 0)
1193: thread->sleep_time += ticks;
1194: else
1195: thread->sleep_time = 0;
1196:
1197: /*
1198: * If asleep for more than 30 seconds forget all
1199: * cpu_usage, else catch up on missed aging.
1200: * 5/8 ** n is approximated by the two shifts
1201: * in the wait_shift array.
1202: */
1203: thread->sched_stamp += ticks;
1204: thread_timer_delta(thread);
1205: if (ticks > 30) {
1206: thread->cpu_usage = 0;
1207: thread->sched_usage = 0;
1208: }
1209: else {
1210: thread->cpu_usage += thread->cpu_delta;
1211: thread->sched_usage += thread->sched_delta;
1212: shiftp = &wait_shift[ticks];
1213: if (shiftp->shift2 > 0) {
1214: thread->cpu_usage =
1215: (thread->cpu_usage >> shiftp->shift1) +
1216: (thread->cpu_usage >> shiftp->shift2);
1217: thread->sched_usage =
1218: (thread->sched_usage >> shiftp->shift1) +
1219: (thread->sched_usage >> shiftp->shift2);
1220: }
1221: else {
1222: thread->cpu_usage =
1223: (thread->cpu_usage >> shiftp->shift1) -
1224: (thread->cpu_usage >> -(shiftp->shift2));
1225: thread->sched_usage =
1226: (thread->sched_usage >> shiftp->shift1) -
1227: (thread->sched_usage >> -(shiftp->shift2));
1228: }
1229: }
1230: thread->cpu_delta = 0;
1231: thread->sched_delta = 0;
1232: /*
1233: * Recompute priority if appropriate.
1234: */
1235: if (
1236: #if MACH_FIXPRI
1237: (thread->policy != POLICY_FIXEDPRI) &&
1238: #endif /* MACH_FIXPRI */
1239: (thread->depress_priority < 0)) {
1240: do_priority_computation(thread, temp_pri);
1241: thread->sched_pri = temp_pri;
1242: }
1243: }
1244:
1245: /*
1246: * run_queue_enqueue for thread_setrun().
1247: */
1248: run_queue_enqueue(rq, th)
1249: run_queue_t rq;
1250: thread_t th;
1251: {
1252: register unsigned int whichq;
1253:
1254: whichq = th->sched_pri;
1255: if (whichq >= NRQS) {
1256: printf("run_queue_enqueue: pri too high (%d)\n", th->sched_pri);
1257: whichq = NRQS - 1;
1258: }
1259:
1260: simple_lock(&rq->lock); /* lock the run queue */
1261: enqueue_tail(&rq->runq[whichq], (queue_entry_t) th);
1262:
1263: if (whichq > rq->high || rq->count == 0)
1264: rq->high = whichq; /* maximize */
1265:
1266: rq->count++;
1267: th->runq = rq;
1268: #if RUNQ_DEBUG
1269: THREAD_CHECK(th, rq);
1270: CHECKRQ(rq, "run_queue_enqueue");
1271: #endif /* DEBUG */
1272: simple_unlock(&rq->lock);
1273: }
1274:
1275:
1276: /*
1277: * thread_setrun:
1278: *
1279: * Make thread runnable; dispatch directly onto an idle processor
1280: * if possible. Else put on appropriate run queue (processor
1281: * if bound, else processor set. Caller must have lock on thread.
1282: * This is always called at splsched.
1283: */
1284:
1285: void thread_setrun(
1286: register thread_t th,
1287: boolean_t may_preempt)
1288: {
1289: register processor_t processor;
1290: register run_queue_t rq;
1291: #if NCPUS > 1
1292: register processor_set_t pset;
1293: #endif /* NCPUS > 1 */
1294:
1295: /*
1296: * Update priority if needed.
1297: */
1298: if (th->sched_stamp != sched_tick) {
1299: update_priority(th);
1300: }
1301:
1302: assert(th->runq == RUN_QUEUE_NULL);
1303:
1304: #if NCPUS > 1
1305: /*
1306: * Try to dispatch the thread directly onto an idle processor.
1307: */
1308: if ((processor = th->bound_processor) == PROCESSOR_NULL) {
1309: /*
1310: * Not bound, any processor in the processor set is ok.
1311: */
1312: pset = th->processor_set;
1313: #if HW_FOOTPRINT
1314: /*
1315: * But first check the last processor it ran on.
1316: */
1317: processor = th->last_processor;
1318: if (processor->state == PROCESSOR_IDLE) {
1319: simple_lock(&processor->lock);
1320: simple_lock(&pset->idle_lock);
1321: if ((processor->state == PROCESSOR_IDLE)
1322: #if MACH_HOST
1323: && (processor->processor_set == pset)
1324: #endif /* MACH_HOST */
1325: ) {
1326: queue_remove(&pset->idle_queue, processor,
1327: processor_t, processor_queue);
1328: pset->idle_count--;
1329: processor->next_thread = th;
1330: processor->state = PROCESSOR_DISPATCHING;
1331: simple_unlock(&pset->idle_lock);
1332: simple_unlock(&processor->lock);
1333: return;
1334: }
1335: simple_unlock(&pset->idle_lock);
1336: simple_unlock(&processor->lock);
1337: }
1338: #endif /* HW_FOOTPRINT */
1339:
1340: if (pset->idle_count > 0) {
1341: simple_lock(&pset->idle_lock);
1342: if (pset->idle_count > 0) {
1343: processor = (processor_t) queue_first(&pset->idle_queue);
1344: queue_remove(&(pset->idle_queue), processor, processor_t,
1345: processor_queue);
1346: pset->idle_count--;
1347: processor->next_thread = th;
1348: processor->state = PROCESSOR_DISPATCHING;
1349: simple_unlock(&pset->idle_lock);
1350: return;
1351: }
1352: simple_unlock(&pset->idle_lock);
1353: }
1354: rq = &(pset->runq);
1355: run_queue_enqueue(rq,th);
1356: /*
1357: * Preempt check
1358: */
1359: if (may_preempt &&
1360: #if MACH_HOST
1361: (pset == current_processor()->processor_set) &&
1362: #endif /* MACH_HOST */
1363: (current_thread()->sched_pri < th->sched_pri)) {
1364: /*
1365: * Turn off first_quantum to allow csw.
1366: */
1367: current_processor()->first_quantum = FALSE;
1368: ast_on(cpu_number(), AST_BLOCK);
1369: }
1370: }
1371: else {
1372: /*
1373: * Bound, can only run on bound processor. Have to lock
1374: * processor here because it may not be the current one.
1375: */
1376: if (processor->state == PROCESSOR_IDLE) {
1377: simple_lock(&processor->lock);
1378: pset = processor->processor_set;
1379: simple_lock(&pset->idle_lock);
1380: if (processor->state == PROCESSOR_IDLE) {
1381: queue_remove(&pset->idle_queue, processor,
1382: processor_t, processor_queue);
1383: pset->idle_count--;
1384: processor->next_thread = th;
1385: processor->state = PROCESSOR_DISPATCHING;
1386: simple_unlock(&pset->idle_lock);
1387: simple_unlock(&processor->lock);
1388: return;
1389: }
1390: simple_unlock(&pset->idle_lock);
1391: simple_unlock(&processor->lock);
1392: }
1393: rq = &(processor->runq);
1394: run_queue_enqueue(rq,th);
1395:
1396: /*
1397: * Cause ast on processor if processor is on line.
1398: *
1399: * XXX Don't do this remotely to master because this will
1400: * XXX send an interprocessor interrupt, and that's too
1401: * XXX expensive for all the unparallelized U*x code.
1402: */
1403: if (processor == current_processor()) {
1404: ast_on(cpu_number(), AST_BLOCK);
1405: }
1406: else if ((processor != master_processor) &&
1407: (processor->state != PROCESSOR_OFF_LINE)) {
1408: cause_ast_check(processor);
1409: }
1410: }
1411: #else /* NCPUS > 1 */
1412: /*
1413: * XXX should replace queue with a boolean in this case.
1414: */
1415: if (default_pset.idle_count > 0) {
1416: processor = (processor_t) queue_first(&default_pset.idle_queue);
1417: queue_remove(&default_pset.idle_queue, processor,
1418: processor_t, processor_queue);
1419: default_pset.idle_count--;
1420: processor->next_thread = th;
1421: processor->state = PROCESSOR_DISPATCHING;
1422: return;
1423: }
1424: if (th->bound_processor == PROCESSOR_NULL) {
1425: rq = &(default_pset.runq);
1426: }
1427: else {
1428: rq = &(master_processor->runq);
1429: ast_on(cpu_number(), AST_BLOCK);
1430: }
1431: run_queue_enqueue(rq,th);
1432:
1433: /*
1434: * Preempt check
1435: */
1436: if (may_preempt && (current_thread()->sched_pri < th->sched_pri)) {
1437: /*
1438: * Turn off first_quantum to allow context switch.
1439: */
1440: current_processor()->first_quantum = FALSE;
1441: ast_on(cpu_number(), AST_BLOCK);
1442: }
1443: #endif /* NCPUS > 1 */
1444: }
1445:
1446: /*
1447: * set_pri:
1448: *
1449: * Set the priority of the specified thread to the specified
1450: * priority. This may cause the thread to change queues.
1451: *
1452: * The thread *must* be locked by the caller.
1453: */
1454:
1455: void set_pri(
1456: thread_t th,
1457: int pri,
1458: boolean_t resched)
1459: {
1460: register struct run_queue *rq;
1461:
1462: rq = rem_runq(th);
1463: th->sched_pri = pri;
1464: if (rq != RUN_QUEUE_NULL) {
1465: if (resched)
1466: thread_setrun(th, TRUE);
1467: else
1468: run_queue_enqueue(rq, th);
1469: }
1470: }
1471:
1472: /*
1473: * rem_runq:
1474: *
1475: * Remove a thread from its run queue.
1476: * The run queue that the process was on is returned
1477: * (or RUN_QUEUE_NULL if not on a run queue). Thread *must* be locked
1478: * before calling this routine. Unusual locking protocol on runq
1479: * field in thread structure makes this code interesting; see thread.h.
1480: */
1481:
1482: struct run_queue *rem_runq(
1483: thread_t th)
1484: {
1485: register struct run_queue *rq;
1486:
1487: rq = th->runq;
1488: /*
1489: * If rq is RUN_QUEUE_NULL, the thread will stay out of the
1490: * run_queues because the caller locked the thread. Otherwise
1491: * the thread is on a runq, but could leave.
1492: */
1493: if (rq != RUN_QUEUE_NULL) {
1494: simple_lock(&rq->lock);
1495: #if RUNQ_DEBUG
1496: CHECKRQ(rq, "rem_runq: at entry");
1497: #endif /* DEBUG */
1498: if (rq == th->runq) {
1499: /*
1500: * Thread is in a runq and we have a lock on
1501: * that runq.
1502: */
1503: #if RUNQ_DEBUG
1504: CHECKRQ(rq, "rem_runq: before removing thread");
1505: THREAD_CHECK(th, rq);
1506: #endif /* DEBUG */
1507: remqueue(&rq->runq[0], (queue_entry_t) th);
1508: rq->count--;
1509: #if RUNQ_DEBUG
1510: CHECKRQ(rq, "rem_runq: after removing thread");
1511: #endif /* DEBUG */
1512: th->runq = RUN_QUEUE_NULL;
1513: simple_unlock(&rq->lock);
1514: }
1515: else {
1516: /*
1517: * The thread left the runq before we could
1518: * lock the runq. It is not on a runq now, and
1519: * can't move again because this routine's
1520: * caller locked the thread.
1521: */
1522: simple_unlock(&rq->lock);
1523: rq = RUN_QUEUE_NULL;
1524: }
1525: }
1526:
1527: return rq;
1528: }
1529:
1530:
1531: /*
1532: * choose_thread:
1533: *
1534: * Choose a thread to execute. The thread chosen is removed
1535: * from its run queue. Note that this requires only that the runq
1536: * lock be held.
1537: *
1538: * Strategy:
1539: * Check processor runq first; if anything found, run it.
1540: * Else check pset runq; if nothing found, return idle thread.
1541: *
1542: * Second line of strategy is implemented by choose_pset_thread.
1543: * This is only called on processor startup and when thread_block
1544: * thinks there's something in the processor runq.
1545: */
1546:
1547: thread_t choose_thread(
1548: processor_t myprocessor)
1549: {
1550: thread_t th;
1551: register queue_t q;
1552: register run_queue_t runq;
1553: register int i;
1554: register processor_set_t pset;
1555:
1556: runq = &myprocessor->runq;
1557:
1558: simple_lock(&runq->lock);
1559: if (runq->count > 0) {
1560: q = runq->runq + runq->high;
1561: for (i = runq->high; i >= 0 ; i--, q--) {
1562: if (!queue_empty(q)) {
1563: th = (thread_t) dequeue_head(q);
1564: th->runq = RUN_QUEUE_NULL;
1565: runq->count--;
1566: runq->high = i;
1567: simple_unlock(&runq->lock);
1568: return(th);
1569: }
1570: }
1571: panic("choose_thread");
1572: /*NOTREACHED*/
1573: }
1574: simple_unlock(&runq->lock);
1575:
1576: pset = myprocessor->processor_set;
1577:
1578: simple_lock(&pset->runq.lock);
1579: return choose_pset_thread(myprocessor,pset);
1580: }
1581:
1582: /*
1583: * choose_pset_thread: choose a thread from processor_set runq or
1584: * set processor idle and choose its idle thread.
1585: *
1586: * Caller must be at splsched and have a lock on the runq. This
1587: * lock is released by this routine. myprocessor is always the current
1588: * processor, and pset must be its processor set.
1589: * This routine chooses and removes a thread from the runq if there
1590: * is one (and returns it), else it sets the processor idle and
1591: * returns its idle thread.
1592: */
1593:
1594: thread_t choose_pset_thread(
1595: register processor_t myprocessor,
1596: processor_set_t pset)
1597: {
1598: register run_queue_t runq;
1599: register thread_t th;
1600: register queue_t q;
1601: register int i;
1602:
1603: runq = &pset->runq;
1604:
1605: if (runq->count > 0) {
1606: q = runq->runq + runq->high;
1607: for (i = runq->high; i >= 0 ; i--, q--) {
1608: if (!queue_empty(q)) {
1609: th = (thread_t) dequeue_head(q);
1610: th->runq = RUN_QUEUE_NULL;
1611: runq->count--;
1612: /*
1613: * For POLICY_FIXEDPRI, runq->low must be
1614: * accurate!
1615: */
1616: #if MACH_FIXPRI
1617: if ((runq->count > 0) &&
1618: (pset->policies & POLICY_FIXEDPRI)) {
1619: while (queue_empty(q)) {
1620: q--;
1621: i--;
1622: }
1623: }
1624: #endif /* MACH_FIXPRI */
1625: runq->high = i;
1626: #if RUNQ_DEBUG
1627: CHECKRQ(runq, "choose_pset_thread");
1628: #endif /* DEBUG */
1629: simple_unlock(&runq->lock);
1630: return th;
1631: }
1632: }
1633: panic("choose_pset_thread");
1634: /*NOTREACHED*/
1635: }
1636: simple_unlock(&runq->lock);
1637:
1638: /*
1639: * Nothing is runnable, so set this processor idle if it
1640: * was running. If it was in an assignment or shutdown,
1641: * leave it alone. Return its idle thread.
1642: */
1643: simple_lock(&pset->idle_lock);
1644: if (myprocessor->state == PROCESSOR_RUNNING) {
1645: myprocessor->state = PROCESSOR_IDLE;
1646: /*
1647: * XXX Until it goes away, put master on end of queue, others
1648: * XXX on front so master gets used last.
1649: */
1650: if (myprocessor == master_processor) {
1651: queue_enter(&(pset->idle_queue), myprocessor,
1652: processor_t, processor_queue);
1653: }
1654: else {
1655: queue_enter_first(&(pset->idle_queue), myprocessor,
1656: processor_t, processor_queue);
1657: }
1658:
1659: pset->idle_count++;
1660: }
1661: simple_unlock(&pset->idle_lock);
1662:
1663: return myprocessor->idle_thread;
1664: }
1665:
1666: /*
1667: * no_dispatch_count counts number of times processors go non-idle
1668: * without being dispatched. This should be very rare.
1669: */
1670: int no_dispatch_count = 0;
1671:
1672: /*
1673: * This is the idle thread, which just looks for other threads
1674: * to execute.
1675: */
1676:
1677: void idle_thread_continue(void)
1678: {
1679: register processor_t myprocessor;
1680: register volatile thread_t *threadp;
1681: register volatile int *gcount;
1682: register volatile int *lcount;
1683: register thread_t new_thread;
1684: register int state;
1685: int mycpu;
1686: spl_t s;
1687:
1688: mycpu = cpu_number();
1689: myprocessor = current_processor();
1690: threadp = (volatile thread_t *) &myprocessor->next_thread;
1691: lcount = (volatile int *) &myprocessor->runq.count;
1692:
1693: while (TRUE) {
1694: #ifdef MARK_CPU_IDLE
1695: MARK_CPU_IDLE(mycpu);
1696: #endif /* MARK_CPU_IDLE */
1697:
1698: #if MACH_HOST
1699: gcount = (volatile int *)
1700: &myprocessor->processor_set->runq.count;
1701: #else /* MACH_HOST */
1702: gcount = (volatile int *) &default_pset.runq.count;
1703: #endif /* MACH_HOST */
1704:
1705: /*
1706: * This cpu will be dispatched (by thread_setrun) by setting next_thread
1707: * to the value of the thread to run next. Also check runq counts.
1708: */
1709: while ((*threadp == (volatile thread_t)THREAD_NULL) &&
1710: (*gcount == 0) && (*lcount == 0)) {
1711:
1712: /* check for ASTs while we wait */
1713:
1714: if (need_ast[mycpu] &~ AST_SCHEDULING) {
1715: (void) splsched();
1716: /* don't allow scheduling ASTs */
1717: need_ast[mycpu] &= ~AST_SCHEDULING;
1718: (void) spl0();
1719: }
1720:
1721: /*
1722: * machine_idle is a machine dependent function,
1723: * to conserve power.
1724: */
1725: }
1726:
1727: #ifdef MARK_CPU_ACTIVE
1728: MARK_CPU_ACTIVE(mycpu);
1729: #endif /* MARK_CPU_ACTIVE */
1730:
1731: s = splsched();
1732:
1733: /*
1734: * This is not a switch statement to avoid the
1735: * bounds checking code in the common case.
1736: */
1737: retry:
1738: state = myprocessor->state;
1739: if (state == PROCESSOR_DISPATCHING) {
1740: /*
1741: * Commmon case -- cpu dispatched.
1742: */
1743: new_thread = (thread_t) *threadp;
1744: *threadp = (volatile thread_t) THREAD_NULL;
1745: myprocessor->state = PROCESSOR_RUNNING;
1746: /*
1747: * set up quantum for new thread.
1748: */
1749: #if MACH_FIXPRI
1750: if (new_thread->policy != POLICY_FIXEDPRI) {
1751: #endif /* MACH_FIXPRI */
1752: /*
1753: * Just use set quantum. No point in
1754: * checking for shorter local runq quantum;
1755: * csw_needed will handle correctly.
1756: */
1757: #if MACH_HOST
1758: myprocessor->quantum = new_thread->
1759: processor_set->set_quantum;
1760: #else /* MACH_HOST */
1761: myprocessor->quantum =
1762: default_pset.set_quantum;
1763: #endif /* MACH_HOST */
1764:
1765: #if MACH_FIXPRI
1766: }
1767: else {
1768: /*
1769: * POLICY_FIXEDPRI
1770: */
1771: myprocessor->quantum = new_thread->sched_data;
1772: }
1773: #endif /* MACH_FIXPRI */
1774: myprocessor->first_quantum = TRUE;
1775: counter(c_idle_thread_handoff++);
1776: thread_run(idle_thread_continue, new_thread);
1777: }
1778: else if (state == PROCESSOR_IDLE) {
1779: register processor_set_t pset;
1780:
1781: pset = myprocessor->processor_set;
1782: simple_lock(&pset->idle_lock);
1783: if (myprocessor->state != PROCESSOR_IDLE) {
1784: /*
1785: * Something happened, try again.
1786: */
1787: simple_unlock(&pset->idle_lock);
1788: goto retry;
1789: }
1790: /*
1791: * Processor was not dispatched (Rare).
1792: * Set it running again.
1793: */
1794: no_dispatch_count++;
1795: pset->idle_count--;
1796: queue_remove(&pset->idle_queue, myprocessor,
1797: processor_t, processor_queue);
1798: myprocessor->state = PROCESSOR_RUNNING;
1799: simple_unlock(&pset->idle_lock);
1800: counter(c_idle_thread_block++);
1801: thread_block_with_continuation(idle_thread_continue);
1802: }
1803: else if ((state == PROCESSOR_ASSIGN) ||
1804: (state == PROCESSOR_SHUTDOWN)) {
1805: /*
1806: * Changing processor sets, or going off-line.
1807: * Release next_thread if there is one. Actual
1808: * thread to run is on a runq.
1809: */
1810: if ((new_thread = (thread_t)*threadp)!= THREAD_NULL) {
1811: *threadp = (volatile thread_t) THREAD_NULL;
1812: thread_setrun(new_thread, FALSE);
1813: }
1814:
1815: counter(c_idle_thread_block++);
1816: thread_block_with_continuation(idle_thread_continue);
1817: }
1818: else {
1819: printf(" Bad processor state %d (Cpu %d)\n",
1820: cpu_state(mycpu), mycpu);
1821: panic("idle_thread");
1822: }
1823:
1824: (void) splx(s);
1825: }
1826: }
1827:
1828: void idle_thread(void)
1829: {
1830: register thread_t self = current_thread();
1831: spl_t s;
1832:
1833: stack_privilege(self);
1834:
1835: s = splsched();
1836: self->priority = 0;
1837: self->sched_pri = 0;
1838:
1839: /*
1840: * Set the idle flag to indicate that this is an idle thread,
1841: * enter ourselves in the idle array, and thread_block() to get
1842: * out of the run queues (and set the processor idle when we
1843: * run next time).
1844: */
1845: thread_lock(self);
1846: self->state |= TH_IDLE;
1847: thread_unlock(self);
1848: current_processor()->idle_thread = self;
1849: (void) splx(s);
1850:
1851: counter(c_idle_thread_block++);
1852: thread_block_with_continuation(idle_thread_continue);
1853: idle_thread_continue();
1854: /*NOTREACHED*/
1855: }
1856:
1857: /*
1858: * sched_thread: scheduler thread.
1859: *
1860: * This thread handles periodic calculations in the scheduler that
1861: * we don't want to do at interrupt level. This allows us to
1862: * avoid blocking.
1863: */
1864: void sched_thread_continue(void)
1865: {
1866: /*
1867: * Compute the scheduler load factors.
1868: */
1869: compute_mach_factor();
1870:
1871: /*
1872: * Scan the run queues for runnable threads that need to
1873: * have their priorities recalculated.
1874: */
1875: do_thread_scan();
1876:
1877: assert_wait((event_t) 0, FALSE);
1878: counter(c_sched_thread_block++);
1879: thread_block_with_continuation(sched_thread_continue);
1880: /*NOTREACHED*/
1881: }
1882:
1883: void sched_thread(void)
1884: {
1885: sched_thread_id = current_thread();
1886:
1887: /*
1888: * Sleep on event 0, recompute_priorities() will awaken
1889: * us by calling clear_wait().
1890: */
1891: assert_wait((event_t) 0, FALSE);
1892: counter(c_sched_thread_block++);
1893: thread_block_with_continuation(sched_thread_continue);
1894: sched_thread_continue();
1895: /*NOTREACHED*/
1896: }
1897:
1898: #define MAX_STUCK_THREADS 128
1899:
1900: /*
1901: * do_thread_scan: scan for stuck threads. A thread is stuck if
1902: * it is runnable but its priority is so low that it has not
1903: * run for several seconds. Its priority should be higher, but
1904: * won't be until it runs and calls update_priority. The scanner
1905: * finds these threads and does the updates.
1906: *
1907: * Scanner runs in two passes. Pass one squirrels likely
1908: * thread ids away in an array, and removes them from the run queue.
1909: * Pass two does the priority updates. This is necessary because
1910: * the run queue lock is required for the candidate scan, but
1911: * cannot be held during updates [set_pri will deadlock].
1912: *
1913: * Array length should be enough so that restart isn't necessary,
1914: * but restart logic is included. Does not scan processor runqs.
1915: *
1916: */
1917:
1918: boolean_t do_thread_scan_debug = FALSE;
1919:
1920: thread_t stuck_threads[MAX_STUCK_THREADS];
1921: int stuck_count = 0;
1922:
1923: /*
1924: * do_runq_scan is the guts of pass 1. It scans a runq for
1925: * stuck threads. A boolean is returned indicating whether
1926: * it ran out of space.
1927: */
1928:
1929: boolean_t
1930: do_runq_scan(
1931: run_queue_t runq)
1932: {
1933: register spl_t s;
1934: register queue_t q;
1935: register thread_t thread;
1936: register int count;
1937:
1938: s = splsched();
1939: simple_lock(&runq->lock);
1940: if((count = runq->count) > 0) {
1941: q = runq->runq + runq->high;
1942: while (count > 0) {
1943: thread = (thread_t) queue_first(q);
1944: while (!queue_end(q, (queue_entry_t) thread)) {
1945: /*
1946: * Get the next thread now, since we may
1947: * remove this thread from the run queue.
1948: */
1949: thread_t next = (thread_t) queue_next(&thread->links);
1950:
1951: if ((thread->state & TH_SCHED_STATE) == TH_RUN &&
1952: thread->sched_stamp != sched_tick) {
1953: /*
1954: * Stuck, save its id for later.
1955: */
1956: if (stuck_count == MAX_STUCK_THREADS) {
1957: /*
1958: * !@#$% No more room.
1959: */
1960: simple_unlock(&runq->lock);
1961: splx(s);
1962: return TRUE;
1963: }
1964: /*
1965: * We can`t take the thread_lock here,
1966: * since we already have the runq lock.
1967: * So we can`t grab a reference to the
1968: * thread. However, a thread that is
1969: * in RUN state cannot be deallocated
1970: * until it stops running. If it isn`t
1971: * on the runq, then thread_halt cannot
1972: * see it. So we remove the thread
1973: * from the runq to make it safe.
1974: */
1975: remqueue(q, (queue_entry_t) thread);
1976: runq->count--;
1977: thread->runq = RUN_QUEUE_NULL;
1978:
1979: stuck_threads[stuck_count++] = thread;
1980: if (do_thread_scan_debug)
1981: printf("do_runq_scan: adding thread %#x\n", thread);
1982: }
1983: count--;
1984: thread = next;
1985: }
1986: q--;
1987: }
1988: }
1989: simple_unlock(&runq->lock);
1990: splx(s);
1991:
1992: return FALSE;
1993: }
1994:
1995: void do_thread_scan(void)
1996: {
1997: register spl_t s;
1998: register boolean_t restart_needed = 0;
1999: register thread_t thread;
2000: #if MACH_HOST
2001: register processor_set_t pset;
2002: #endif /* MACH_HOST */
2003:
2004: do {
2005: #if MACH_HOST
2006: simple_lock(&all_psets_lock);
2007: queue_iterate(&all_psets, pset, processor_set_t, all_psets) {
2008: if (restart_needed = do_runq_scan(&pset->runq))
2009: break;
2010: }
2011: simple_unlock(&all_psets_lock);
2012: #else /* MACH_HOST */
2013: restart_needed = do_runq_scan(&default_pset.runq);
2014: #endif /* MACH_HOST */
2015: if (!restart_needed)
2016: restart_needed = do_runq_scan(&master_processor->runq);
2017:
2018: /*
2019: * Ok, we now have a collection of candidates -- fix them.
2020: */
2021:
2022: while (stuck_count > 0) {
2023: thread = stuck_threads[--stuck_count];
2024: stuck_threads[stuck_count] = THREAD_NULL;
2025: s = splsched();
2026: thread_lock(thread);
2027: if ((thread->state & TH_SCHED_STATE) == TH_RUN) {
2028: /*
2029: * Do the priority update. Call
2030: * thread_setrun because thread is
2031: * off the run queues.
2032: */
2033: update_priority(thread);
2034: thread_setrun(thread, TRUE);
2035: }
2036: thread_unlock(thread);
2037: splx(s);
2038: }
2039: } while (restart_needed);
2040: }
2041:
2042: /*
2043: * Just in case someone doesn't use the macro
2044: */
2045: #undef thread_wakeup
2046: void thread_wakeup(x)
2047: void *x;
2048: {
2049: thread_wakeup_with_result(x, THREAD_AWAKENED);
2050: }
2051:
2052: #if RUNQ_DEBUG
2053: void checkrq(
2054: run_queue_t rq,
2055: char *msg)
2056: {
2057: register queue_t q1;
2058: register int i, j;
2059: register queue_entry_t e;
2060: register int high;
2061:
2062: high = NRQS;
2063: j = 0;
2064: q1 = &rq->runq[NRQS-1];
2065: for (i = NRQS-1; i >= 0; i--) {
2066: if (q1->next == q1) {
2067: if (q1->prev != q1)
2068: panic("checkrq: empty at %s", msg);
2069: }
2070: else {
2071: if (high == NRQS)
2072: high = i;
2073:
2074: for (e = q1->next; e != q1; e = e->next) {
2075: j++;
2076: if (e->next->prev != e)
2077: panic("checkrq-2 at %s", msg);
2078: if (e->prev->next != e)
2079: panic("checkrq-3 at %s", msg);
2080: }
2081: }
2082: q1--;
2083: }
2084: if (j != rq->count)
2085: panic("checkrq: count %d wrong at %s (should be %d)",
2086: j, msg, rq->count);
2087: if (rq->count != 0 && high > rq->high)
2088: panic("checkrq: high %d wrong at %s (should be %d)",
2089: high, msg, rq->high);
2090: }
2091:
2092: void thread_check(
2093: register thread_t th,
2094: register run_queue_t rq)
2095: {
2096: register unsigned int whichq;
2097:
2098: whichq = th->sched_pri;
2099: if (whichq >= NRQS) {
2100: panic("thread_check: priority %d too high\n", whichq);
2101: whichq = NRQS-1;
2102: }
2103: if ((th->links.next == &rq->runq[whichq]) &&
2104: (rq->runq[whichq].prev != (queue_entry_t)th))
2105: panic("thread_check");
2106: }
2107: #endif /* DEBUG */
2108:
2109: int thread_wait_result()
2110: {
2111: return current_thread()->wait_result;
2112: }
2113:
2114: void thread_block(void)
2115: {
2116: thread_block_with_continuation((continuation_t) 0);
2117: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.