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