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