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