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